package com.easy.carl.algorithm.String;

/**
 * @ClassName RepeatedSubstringPattern459
 * @Description 459. 重复的子字符串
 * @Author zheng
 * @Date 2021/12/27 17:40
 * @Version 1.0
 **/
public class RepeatedSubstringPattern459 {

    public boolean repeatedSubstringPattern1(String s) {
        for (int i = 1; i <= s.length() / 2; i++) {
            if (s.length() % i == 0) {
                boolean match = true;
                for (int j = i; j < s.length(); j++) {
                    if (s.charAt(j) != s.charAt(j - i)) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return true;
                }
            }
        }
        return false;
    }

    //相等前后缀
    public int[] getNext(String str) {
        int[] next = new int[str.length()];
        int j = 0;
        for (int i = 1; i < str.length(); i++) {
            while (j > 0 && str.charAt(i) != str.charAt(j)) {
                j = next[j - 1];
            }
            //j表示前缀 同时表示相等的前缀子串与相等的后缀子串的最大长度
            if (str.charAt(i) == str.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }

    public boolean repeatedSubstringPattern(String s) {
        //字符串长度为0，不符合条件
        if (s.length() == 0) {
            return false;
        }
        int[] next = getNext(s);
        int len = s.length();
        //数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。
        if (next[len - 1] != 0 && len % (len - next[len - 1]) == 0) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        RepeatedSubstringPattern459 repeatedSubstringPattern459 = new RepeatedSubstringPattern459();
        System.out.println(repeatedSubstringPattern459.repeatedSubstringPattern("aba"));
    }

}
